package offer;

/**
 * @Author SSK
 * @Date Created in 22:55 2019/8/6
 * @Description 二叉树的下一个结点
 * @Version 1.0
 */
public class T58 {
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;

        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    public TreeLinkNode GetNext(TreeLinkNode pNode) {
        if (pNode==null) {
            return pNode;
        }
        if (pNode.right==null) {
            TreeLinkNode fa = pNode.next;
            while (pNode!=null&&fa!=null&&fa.right==pNode) {
                pNode = pNode.next;
                fa = pNode.next;
            }
            if (fa==null||fa.left != pNode) {
                return null;
            }
            return fa;
        }
        pNode = pNode.right;
        while (pNode.left!=null) {
            pNode = pNode.left;
        }
        return pNode;
    }
}
